package com.qrpcw.algorithms;
import java.util.Arrays;

public class QuickSortTest {

	public static void main(String[] args) {
		int[] a = new int[]{16,14,10,8,7,9,3,2,4,11,5,1,6};
		QuickSortTest test = new QuickSortTest();
		test.qSort(a);
		System.out.println(Arrays.toString(a));
	}
	
	public void exchange(int[] A, int i,int j){
		int temp; 
		temp = A[i]; A[i] = A[j]; A[j] = temp;
	}
	
	public void qSort(int[] A){ quickSort(A,0,A.length-1);}
	
	public void quickSort(int[] A,int p,int r){
		if(p < r){
			int q = partition(A,p,r);
			quickSort(A,p,q-1);
			quickSort(A,q+1,r);
		}
	}
	
	public int partition(int[] A,int p,int r){
		int x = A[r];
		int i = p-1;
		for(int j=p; j<r; j++){
			if(A[j]<= x){
				i = i+1;
				exchange(A,i,j);
			}
		}
		exchange(A,i+1,r);
		return i+1;
	}
}
